package list;

public class 两个链表的第一个公共节点_剑指offer52 {
    /**
     * 快慢指针追及问题
     *
     * 链表 a长度 a  链表b长度 b    因此  a + b  = b + a  到尾部前  公共节点后 距离是c
     *  则  a + b -c = b + a -c  交换遍历一定能同时到达节点尾部
     * 往前看  其实在到尾部前  公共节点后一直是同步的  因此第一个相等的节点就是公共节点
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        while(curA != curB){
            if(curA != null) {
                curA = curA.next;
            } else{
                // 一轮以内一定能到达共同点  因此不考虑再换到headA
                curA = headB;
            }
            if(curB != null) {
                curB = curB.next;
            } else {
                curB = headA;
            }
        }
        return curA;
    }
}
class ListNode {
       int val;
       ListNode next;
       ListNode(int x) {
           val = x;
           next = null;
       }
   }


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class 相交链表_160 {
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA, curB = headB;
        while(curA !=curB ){
            if(curA == null) {
                curA = headB;
            }
            // BUG  这样写就移动了两步  由于节点总数是奇数  永不相等  正确写法参上class
            curA = curA.next;
            if(curB == null) {
                curB = headA;
            }
            // BUG  这样写就移动了两步  由于节点总数是奇数  永不相等  正确写法参上class
            curB = curB.next;
        }
        return curA;
    }

    public static void main(String[] args) {
        ListNode a = new ListNode(3);
        ListNode b = new ListNode(2); b.next = a;
        getIntersectionNode(a, b);}
}